package medium

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(N)
空间复杂度:O(N)

二叉树的右侧视图,可以转换为层序遍历中最后一个非空元素
*/

func rightSideView(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	level := []*TreeNode{root}
	res := make([]int, 0)
	for len(level) != 0 {
		rightestVal := level[len(level)-1].Val
		res = append(res, rightestVal)
		var pos int
		for i, node := range level {
			if node != nil {
				if node.Left != nil {
					level = append(level, node.Left)
				}
				if node.Right != nil {
					level = append(level, node.Right)
				}
			}
			// 记录最后一个元素的位置
			pos = i
		}
		// 将上一层的元素去除
		level = level[pos+1:]
	}
	return res
}
